|
|
Algoritmická složitost řešení ve vybraných třídách nekooperativních her
Wichera, Adam ; Majer, Ondřej (vedoucí práce) ; Kroupa, Tomáš (oponent)
Název práce: Algoritmická složitost řešení ve vybraných třídách nekooperativních her Autor: Adam Wichera Katedra (ústav): Katedra logiky Vedoucí bakalářské práce: RNDr. Ondřej Majer, CSc. e-mail vedoucího: majer@ u.cas.cz Abstrakt V předložené práci studujeme přirozené algoritmické problémy vyvstávající z pojmu Nashova equilibria. Problém jeho existence je triviální, protože plyne z Nashova důkazu úplnosti. Ani příslušný vyhledávací problém se tedy nezdá být NP-úplný a to právě proto, že existence ře- šení je zaručena. Zajímavé ale je, že jakékoli přirozené rozšíření tohoto problému už se zdá být NP-úplné. U mnohých už byla NP-úplnost pro konečné nekooperativní hry s obecným součtem dávno dokázána, většinou redukcí problému SAT, Klikového problému, nebo množinového pro- blému hledajícího podpokrytí. Ovšem zda se k ostatním řadí i problém existence asymetrického equilibria pro symetrické hry, byl otevřený problém. Zde ukážeme, jak zobecnit důkaz z [? ] tak, aby dokázal postihnout i problém asymetrických Equilibrií a dokážeme tak jeho NP-kompletnost. Klíčová slova: Nashovo equilibrium, Algoritmická složitost, Nekooperativní hry, Teorie her, Asymetrické equilibrium, 1
|
host ::
RSS.